#ifndef GML__ALGO_H
#define GML__ALGO_H

#include "config.h"

#define max(_a, _b) ({ \
    defineArg(_a, __a); \
    defineArg(_b, __b); \
    __a > __b ? __a : __b; \
})

#define min(_a, _b) ({ \
    defineArg(_a, __a); \
    defineArg(_b, __b); \
    __a < __b ? __a : __b; \
})

#define median(_a, _b, _c) ({ \
    defineArg(_a, __a); \
    defineArg(_b, __b); \
    defineArg(_c, __c); \
    __typeof__(__a) __ret; \
    if (__a < __b) { \
        if (__b < __c) { \
            __ret = __b; \
        } \
        else if (__a < __c) { \
            __ret = __c; \
        } \
        else { \
            __ret = __a; \
        } \
    } \
    else if (__a < __c) { \
        __ret = __a; \
    } \
    else if (__b < __c) { \
        __ret = __c; \
    } \
    else { \
        __ret = __b; \
    } \
    __ret; \
})

#define swap(_a, _b) ({ \
    defineArg(_a, __a); \
    defineArg(_b, __b); \
    __typeof__(*__a) __temp = *__a; \
    *__a = *__b; \
    *__b = __temp; \
})

#define loopSearch(_T, _first, _last, _value) ({ \
    defineArg(_first, __first); \
    defineArg(_last, __last); \
    defineArg(_value, __value); \
    for (; _T##Func(IteratorNotEqualTo)(&__first, &__last); _T##Func(IteratorIncreasePrefix)(&__first)) { \
        if (__value == *_T##Func(IteratorIndirect)(&__first)) { \
            break; \
        }; \
    } \
    __first; \
})

#define loopLowerBound(_T, _first, _last, _value) ({ \
    defineArg(_first, __first); \
    defineArg(_last, __last); \
    defineArg(_value, __value); \
    for (; !_T##Func(IteratorEqualTo)(&__first, &__last); _T##Func(IteratorIncreasePrefix)(&__first)) { \
        if (__value <= *_T##Func(IteratorIndirect)(&__first)) { \
            break; \
        } \
    } \
    __first; \
})

#define loopUpperBound(_T, _first, _last, _value) ({ \
    defineArg(_first, __first); \
    defineArg(_last, __last); \
    defineArg(_value, __value); \
    for (; !_T##Func(IteratorEqualTo)(&__first, &__last); _T##Func(IteratorIncreasePrefix)(&__first)) { \
        if (__value < *_T##Func(IteratorIndirect)(&__first)) { \
            break; \
        } \
    } \
    __first; \
})

#define binarySearch(_T, _first, _last, _value) ({ \
    defineArg(_first, __first); \
    defineArg(_last, __last); \
    defineArg(_value, __value); \
    ptrdiff_t __diff = _T##Func(IteratorDiff)(&__last, &__first); \
    while (__diff > 0) { \
        ptrdiff_t __half = __diff / 2; \
        __typeof__(__first) center = _T##Func(IteratorAdd)(&__first, __half); \
        if (*_T##Func(IteratorIndirect)(&center) < __value) { \
            __first = _T##Func(IteratorAdd)(&center, 1); \
            __diff = __diff - __half - 1; \
        } \
        else { \
            __diff = __half; \
        } \
    } \
    if (__value < *_T##Func(IteratorIndirect)(&__first)) { \
        __last; \
    } \
    else { \
        __first; \
    } \
})

#define binaryLowerBound(_T, _first, _last, _value) ({ \
    defineArg(_first, __first); \
    defineArg(_last, __last); \
    defineArg(_value, __value); \
    ptrdiff_t __diff = _T##Func(IteratorDiff)(&__last, &__first); \
    while (__diff > 0) { \
        ptrdiff_t __half = __diff / 2; \
        __typeof__(__first) center = _T##Func(IteratorAdd)(&__first, __half); \
        if (*_T##Func(IteratorIndirect)(&center) < __value) { \
            __first = _T##Func(IteratorAdd)(&center, 1); \
            __diff = __diff - __half - 1; \
        } \
        else { \
            __diff = __half; \
        } \
    } \
    __first; \
})

#define binaryUpperBound(_T, _first, _last, _value) ({ \
    defineArg(_first, __first); \
    defineArg(_last, __last); \
    defineArg(_value, __value); \
    ptrdiff_t __diff = _T##Func(IteratorDiff)(&__last, &__first); \
    while (__diff > 0) { \
        ptrdiff_t __half = __diff / 2; \
        __typeof__(__first) center = _T##Func(IteratorAdd)(&__first, __half); \
        if (__value < *_T##Func(IteratorIndirect)(&center)) { \
            __diff = __half; \
        } \
        else { \
            __first = _T##Func(IteratorAdd)(&center, 1); \
            __diff = __diff - __half - 1; \
        } \
    } \
    __first; \
})

#define forEach(_T, _iterator, _container) \
    for (_T##Type(Iterator) _iterator = _T##Func(Begin)(&_container), end = _T##Func(End)(&_container); _T##Func(IteratorNotEqualTo)(&_iterator, &end); _T##Func(IteratorIncreasePrefix)(&_iterator))

#endif // GML__ALGO_H
